#include"BinaryTreeNode.h"
#include"Queue.h"

BTNode* BuyNode(const BTDataType data) {
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(1);
	}
	newnode->_data = data;
	newnode->_left = NULL;
	newnode->_right = NULL;
	return newnode;
}

BTNode* PreCreateBT(const int* arr, BTNode* root, int* num, int* i) {
	if (i == NULL || num == NULL || arr == NULL) {
		return NULL;
	}
	if (*i < *num) {
		if (arr[*i] == -1) {
			root = NULL;
			(*i)++;
		}
		else {
			root = BuyNode(arr[(*i)++]);
			root->_left = PreCreateBT(arr, root->_left, num, i);
			root->_right = PreCreateBT(arr, root->_right, num, i);
		}
	}
	return root;
}

BTNode* LevelCreateBT(const BTDataType* arr, BTNode* root, const int* num, int* i) {
	if (arr == NULL || num == NULL || i == NULL) {
		return NULL;
	}
	Queue* tree = QueueCreate();
	QueueInit(tree);
	while(*i < *num) {
		if (*i == 0) {
			root = BuyNode(arr[(*i)++]);
			QueuePush(tree, root);
			if (*i == *num) {
				break;
			}
		}
		BTNode* root_tmp = tree->_front->val;
		root_tmp->_left = BuyNode(arr[(*i)++]);
		QueuePush(tree, root_tmp->_left);
		if (*i == *num) {
			break;
		}
		root_tmp->_right = BuyNode(arr[(*i)++]);
		QueuePush(tree, root_tmp->_right);
		QueuePop(tree);
	}
	QueueDestroy(tree);
	return root;
}

void BinaryTreeDestroy(BTNode* root) {
	if (root) {
		BinaryTreeDestroy(root->_left);
		BinaryTreeDestroy(root->_right);
		free(root);
		root = NULL;
	}
}

void BinaryTreePreOrder(BTNode* root) {
	if (root) {
		printf("%d ", root->_data);
		BinaryTreePreOrder(root->_left);
		BinaryTreePreOrder(root->_right);
	}
}

void BinaryTreeInOrder(BTNode* root) {
	if (root) {
		BinaryTreeInOrder(root->_left);
		printf("%d ", root->_data);
		BinaryTreeInOrder(root->_right);
	}
}

void BinaryTreePostOrder(BTNode* root) {
	if (root) {
		BinaryTreePostOrder(root->_left);
		BinaryTreePostOrder(root->_right);
		printf("%d ", root->_data);
	}
}

int BinaryTreeSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	else {
		return 1 + BinaryTreeSize(root->_left) +
			BinaryTreeSize(root->_right);
	}
}

int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	else if (root->_left == NULL && root->_right == NULL) {
		return 1;
	}
	else {
		return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
	}
}

int BinaryTreeLevelKSize(BTNode* root, int k) {
	if (root == NULL || k == 0) {
		return 0;
	}
	else if (root && k == 1) {
		return 1;
	}
	else {
		return BinaryTreeLevelKSize(root->_left, k - 1) + 
			BinaryTreeLevelKSize(root->_right, k - 1);
	}
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	if (root == NULL) {
		return NULL;
	}
	else if (root->_data == x) {
		return root;
	}
	else {
		BTNode* left = BinaryTreeFind(root->_left, x);
		BTNode* right = BinaryTreeFind(root->_right, x);
		return left != NULL ? left : right;
	}
}

void BinaryTreeLevelOrder(BTNode* root) {
	Queue* a = QueueCreate();
	QueueInit(a);
	QueuePush(a, root);
	while (1) {
		BTNode* tmp = QueueFront(a);
		if (tmp != NULL) {
			printf("%d ", tmp->_data);
			QueuePush(a, tmp->_left);
			QueuePush(a, tmp->_right);
			QueuePop(a);
		}
		else
			break;
	}
	QueueDestroy(a);
	a = NULL;
}

bool BinaryTreeComplete(BTNode* root) {
	Queue* a = QueueCreate();
	QueueInit(a);
	QueuePush(a, root);
	BTNode* tmp = QueueFront(a);
	while (1) {
		tmp = QueueFront(a);
		if (tmp != NULL) {
			QueuePush(a, tmp->_left);
			QueuePush(a, tmp->_right);
			QueuePop(a);
		}
		else {
			QueuePop(a);
			break;
		}
	}
	tmp = QueueFront(a);
	while(a->_front){
		if (tmp) {
			QueueDestroy(a);
			return false;
		}
		else {
			QueuePop(a);
			tmp = QueueFront(a);
		}
	}
	return true;
}